perm filename NOTES.END[LSP,JRA]4 blob
sn#098594 filedate 1974-04-24 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00004 00002 .SEC(Compilation)
C00025 00003 .SS(More on Compilation,compiler)
C00034 00004 .SS(Compilers for subsets of LISP)
C00047 00005 .SS(Problems)
C00048 00006 .SS(One-pass Assemblers,assemblers,P7:)
C00061 00007 .SS(A compiler for simple %3eval%*,compiler,P32:)
C00065 00008 .<<discussion of offset and vpl>>
C00076 00009 Here is a partial sketch of %3compile%* operating on %3j <= λ[[xy]f[g[x]h[y]]].%*
C00080 00010 .SS(A project: Efficient compilation)
C00084 00011 .SS(A project: One-pass assembler)
C00087 00012 .SS(A project: Syntax directed compilation,syntax-directed,P4:)
C00088 00013 .SS(A deep-binding compiler,deep binding)
C00089 00014 .SS(Compilation and global variables,global variables,P5:)
C00097 00015 .SS(Functional Arguments,,P3:)
C00104 00016 .SS(Tracing and debugging in LISP)
C00110 00017 .SS(Macros and special forms,macros,P57:)
C00125 00018 .SS(Numbers,numbers)
C00129 00019 .SEC(Storage structures and efficiency)
C00134 00020 .SS(Bit-tables)
C00136 00021 .SS(Vectors and arrays)
C00143 00022 A typical implementation on an array facility in LISP would include
C00145 00023 .SS(strings and linear LISP,string processor,P27:)
C00155 00024 .SS(%3rplaca%* and %3rplacd%*)
C00160 00025 .SS(Applications of %3rplaca%* and %3rplacd%*)
C00174 00026 .SEC(Systems Organization)
C00196 ENDMK
C⊗;
.SEC(Compilation)
.TURN ON "←";
.SS(On LISP and Semantics)
LISP should be the first language learned by Computer Science majors.
As a mathematical language for studies algorithms for data structures, it is
presently without peer. As you are seeing now, the problems of language implementation and their solutions are describable
quite easily in the implementation of LISP (symbol tables, hashing, garbage
collection, stacks, linked allocation, lists, etc. etc.) At the theoretical
level, questions of provability of properties of programs are tractable. As a
programming language, LISP has exceptionally powerful features possessed by few
languages. In particular the uniform representation of program and data. LISP
is also quite useful in understanding the ⊗→semantics↔← of programming languages. The
study of semantics is motivated by the desire to have a tool for describing
the meaning of constructs of a language; in particular, a tool of the power and
clarity of BNF descriptions of the syntax of languages.
The field of programming language semantics is full of ⊗→bull↔← written by people who don't
understand the problem. Here is some more by another.
There are many different schools of thought concerning appropriate means
for describing semantics.
One thought is to describe the meaning of a language in terms of the process
of compilation. That is, the semantic is specified by some canonical compiler
producing code of some standard machine-independent machine. The meaning of
a program is the outcome of an interpreter interpreting this machine-independent
code.
The key problem is: just what is the semantic specification supposed to
do? If it is truly to help a programmer (be he implementor or applications)
to understand the meaning of a particular constructs, then this proposal is
lacking. To understand a construct now requires that you read the description
of a compiler--a non-trivial task, and understand two machines-- the machine-
independent and the real machine. There is a more fundamental difficulty here.
When you look at a statement of a high-level language you think about the effect
the statement will have on the environment of your program when it executes, you
do not think about the code that gets generated and then think about the
execution of that code. Thus modeling semantics in terms of a compiler model is
addiing one more level of obfuscation. A more natural description of the meaning of
constructs is given in terms of the run-time behavior of these constructs.
That's what LISP does. The %3eval%* function describes the execution sequence of a
representation of an arbitrary LISP expression. Thus %3eval%* is the semantic
description of LISP. Now certain timid souls shrink from this resulting
circularity: the description of the semantics of a language in that language, but
circularity, like death and taxes, is inevitable.
Attempts have been made to give non-circular interpreter-based
descriptions of semantics for languages other than LISP. There is the
incredible VDL description of PL/1; and the convoluted description of ALGOL 68
by a Markov algorithm.
To describe meaning in terms of 'self-evident' string manipulations
is misplaced rigor. If a semantic description is to be anything more than a
sterile game it must be useful to implementors as well as applications
programmers. If you decide to describe the semantics of language L%41%* in a
simpler language L%42%* then either L%42%* is 'self evident' or you must give a
description of the meaning of L%42%*, etc. So either you go circular or you end
up with a (useless) 'self-evident' L%4n%*.
There are very good reasons for deciding on direct circularity. First,
you need only learn one language. If the semantic specification is given
the source language, then you learn the programming language and the
semantic (meta) language at the same time. Second, since the evaluator is
written in the language, we can understand the language by understanding
the workings of the single program, %3eval%*; and if we wish to modify the
semantics we need change only one (source language) program. Thus, if we
wished to add new language constructs to LISP (like the %3prog%* feature) we
need only modify %3eval%* so that it recognizes an occurrence of a (sexpr
representation of a) %3prog%*, add a new (semantic) function to describe the
interpretation of the construct and we're done.
A semantic description should not attempt to explain everything about a language.
You must assume that your reader understands something ... . McCarthy: %2`Nothing
can be explained to a stone'%*.
A semantic description of a language must be natural. It must match the expressive
power of the language. A semantic description should also model how the constructs
are to be implemented on a reasonable machine. What is needed is a semantic
representation which exploits, rather than ignores, the structure of the language.
It can assume a certain level of understanding on the part of the
reader. It need only explain what needs explaining.
Let's look at syntax for a moment. A satisfactory description of much of
programming language syntax is standard BNF. The BNF is a generative, or synthetic
grammar. That is, rewriting rules specifying how to generate well formed
strings are given. A semantic specification on the other hand can be considered
to be a function which takes as input an arbitrary programs and gives as output
a representation of the value of executing the program. This implies that
our semantic function must have some way of analyzing the structure of the program.
.P75:
In 1962, John McCarthy described the concept of abstract ⊗→analytic syntax↔←. It
is analytic in the sense that it tells how to take programs apart.. how to recognize
and select subparts of programs using predicates and selector functions. It is abstract
in the sense that it makes no commitment to the external representation of the
constitutients of the program. We need only be able to recognize the occurrence
of a desired construct. For example:
←isterm[t]%c≡%*isvar[t]%c∨%*isconst[t]%c∨%*(issum[t]∧isterm[addend[t]]∧isterm[augend[t]])
and the BNF equation:
←<term> ::= <var> | <const> | <term> + <term>.
issum, addend, and augend, don't really care whether the sum is represented as:
x+y, or +[x;y] or %3(PLUS X Y)%* or xy+ . The different external representations
are reflections of different ⊗→concrete syntax↔←es. The above BNF equations give one.
What is gained? Since it is reasonable to assume that the semantics is to
operate on some internal representation of the source program, and in fact,
a representation reflecting the structure of the program (commonly known
as a parse tree), we can describe the semantics of a program in terms of a function
which operates on a parse tree using the predicates and selectors of the
analytic syntax. Abstract syntax concerns itself only with those properties
of a program which are of interest to an evaluator.
You may then profitably think of the Meta expression form of LISP as a concrete syntax.
You may think of the M- to S-expression translator as the parser which maps
the external representation onto a parse (or computational) tree. The selectors
and predicates of the analytic syntax are straightforward; recall the BNF for
LISP:
.BEGIN TABIT1(11);GROUP;
<form>\::= <constant>
\::= <variable>
\::=<function>[<arg>; ... <arg>]
\::= [<form> → <form> ... <form> → <form>]
\ ....
.END
Among other things, then, we need to recognize constants (%3isconst%*),
variables (%3isvar%*), conditional expressions (%3iscond%*), and functions
(%3isfun%*).
We would then need to write a function in some language expressing the values
of these constructs. Since the proposed evaluator is to manipulate parse
trees, and since the domain of LISP functions %2is%* binary trees, it should seem
natural to use LISP itself. If this is the case, then we must represent the parse
tree as a LISP sexpr and represent the selectors and recognizers as LISP functions and
predicates.
Perhaps:
.BEGIN SELECT 3;TABIT1(11);GROUP;
isconst[x]\:numberp[x]%c∨%*eq[x;NIL]%c∨%*eq[x;T]%c∨%*eq[car[x];QUOTE]
isvar[x]\:atom[x]%c∧¬%*(eq[x;T]%c∨%*eq[x;NIL]%c∨%*numberp[x])
iscond[x]\:eq[car[x];COND]
.END
So to recapitulate, a concrete syntax for LISP can be conceived of as the normal Mexpr
notation; and abstract syntax for LISP can be formulated in terms of the representation of the
LISP program as a Sexpr. The the description of the semantics of LISP is simply %3eval%*.
There are really two issues here: %2a%* representation of the analytic syntax of a language,
and a representation in terms of the language itself. In conjunction, these two
ideas give a natural and very powerful means of specifying semantics.
If this means of semantic specification %2is%* really all that good (does
all good thing, no bad thing, and takes no time) then we should be able to
specify other languages similarly. What are the weak points of LISP as
`real' programming language? Mainly the insistance on binary tree representations
of data. It is quite clear that many applications could profit from other
data representations. What we would then like is a language which has richer
data structures than LISP but which is designed to allow LISP-style semantic specification.
That is, we will be able to give an analytic syntactic specification for the language.
We will be able to write an evaluator, albeit more complex than %3eval%*, in the language
itself. The evaluator will operate on a representation of the program as a legal
data structure of the language, just as %3eval%* operates on the sexpr translation
of the LISP program. The concrete syntax will be specified as a set of BNF equations,
and our parser will translate legal strings -- programs-- into parse trees.
In outline, to completely specify a construct in LISP we must have the following:
.BEGIN TABIT1(30);GROUP;
\%21.%* A concrete production
**1**\%22.%* An abstract data type
\%23%*. A mapping from %21%* to %22%*.
\%24.%* An evaluator for the abstract type.
.END
The `real' programming language ⊗→EL1↔←, Extensible Language 1, %2has%* in fact been specified in exactly
this manner. We could not begin to describe this language here; rather we will
sketch only a bare outline of the ideas involved. As with LISP, EL1 maps programs
onto data structures. EL1 has richer data types including integers, characters,
pointers, and structures. Its syntax is described in BNF and a mapping from
well-formed syntactic units to data structures is given. The EL1 evaluator
is written in EL1 and manipulates the data-structure representation of EL1 programs
in a manner totally analogous to the LISP %3eval%* function.
As the name implies, a rationale for EL1 was extensibility.
An ⊗→extensible language↔← is supposed to supply a base or core language, which has
sufficient handles such that a user can describe new data structures, new operations,
and new control structures. These new objects are described in terms of
combinations of constructs in the ⊗→base language↔←. Extensibility is implicitly
commited to the premiss that the power of high level languages is
primarily notational rather than computational.
An alternative to extensibility, called ⊗→shell languages↔←, is perhaps
best exemplified by ⊗→PL/1↔←.
`Perhaps the most immediately striking attribute of PL/1 is its bulk'. "bulk"...
that's a polite word for another four-letter expletive. If nothing else
PL/1 should have the beneficial effect of illustrating the absurdity
of languages which attempt to do all things for all people. ?? PL ... political
language?? The sheer size of such languages bodes ill for efficient compilation,
maintanence, and learnability.
PL/1 also suffers for the "committee effect" in language design. No great work of art has
ever been designed "by committee"; there is no reason to believe programming language
design should be any different.
We have frequently seen how easy it has been to extend LISP by modifying %3eval%*.
This is particularly easy because we are making modifications at the level of data-structure represntation
of programs. In EL1 we wish to make the extensions at the level of concrete syntax,
rather than abstract syntax as LISP does.
We can do this by using a parser which is table-driven,
operating on an modifable set of productions. The parser must be capable
of recognizing occurrences of a set %21. - 4.%* of **1** above, adding
%21%* to its set of productions, using %22%* and %23%* to effect the
translations, and using %24%* to effect the evaluation of an instance of %21%*.
This in essence is what EL1 does.
.SS(More on Compilation,compiler)
As we have described in previous notes the processes of evaluation
and compilation are parallel: the evaluator performs the evaluation; the
compiler emits instructions which when executed produce the same computational
effect as the evaluator.
Since the code produced by the compiler is either in machine language
or in a form closer to the machine than the source program, we can execute
the code much faster. A speed-up factor of ten is not uncommon.
Also in LISP we know that programs are stored as sexpressions.
Our compiled code will be machine language, thus freeing a large quantity
of sexpression storage. This will usually make garbage collection
be less time consuming.
Why not compile all programs? We already have seen that we can %3cons%*-up
new expressions to be evaluated while we are running. Still we can force
even those expressions through a compiler before execution. The answer,
rather, is that for debugging and editing of programs it is extremely convenient
to have a structured representation of the program (like sexpression)
in memory. We shall say more about this later.
We shall exploit the analogy between compilers and evaluators when we write the
LISP function, ⊗→%3compile%*↔←, which will describe the compiler.
We shalll do this in two ways. First, the structure of the %3compile%* function
and its subfunctions will be written to capitalize on the knowledge we
have acquired from writing evaluators. Second and more difficult, we will attempt
to abstract from the specific compiler, the essence of LISP compilers without
losing all of the details. At the most general level a compiler simply
produces code which when executed has the same effect as evaluating the original
form, but this description has lost too much detail.
This second task is more difficult because we have to separate two representations
from the specific compiler. We are rrepresenting forms as data structures; and we
are also dealing with the representation of a specific machine.
The task %2is%* worth persuing since we wish to write different compilers
for the same machine and also a single compiler capable of easy transportation to
other machines.
The input to
%3compile%* is the sexpr representation of a LISP function; the output is a list
which represents a sequence of machine instructions. Assume that we have
LISP running on %aBrand X%* machine, and we have just written the LISP function,
%3compile%*, which produces code for %aBrand X%* machine. Then:
.GROUP
1. Write the Sexpression form of %3compile%*.
2. Read in this translation, defining %3compile%*.
3. Ask LISP to evaluate: %3compile[COMPILE]%*.
.APART
Now since %3compile%* is a function of one argument which proports to compile code
for %aBrand X%* machine, translating the sexpression representation of its argument
to machine code, the output of step 3. should be a list of instructions
representing the translation of the function %3compile%*. That is, step 3. compiles
the compiler!!
A technique called %2⊗→bootstrapping↔←%* is closely related to the process described
above. Assume that we have LISP and its compiler running on %aBrand X%*, and
we wish to implement LISP (quickly) on %aBrand Y%*. If we have been careful in
our encoding of the %3compile%* function then %2most%* of %3compile%* is
machine independent, that is it deals mostly with the structure of LISP and
only in a few places deals with the structure of the particular machine. As we
will see this is not too great an assumption to make.
Notice that this is one of our admonitions: encode algorithms in a
representation-independent style and include representation-dependent
rountines to interface with the program. To change representations, simply
requires changing those simpler subfunctions. Here the repesentations are
machines and the algorithm is a compiling function for LISP.
Let us call those parts of the compiler
which deal with the machine, the ⊗→code generators↔←. Now if we understand the
machine organization of brands %aX%* and %aY%* then for any instruction on %aBrand X%*
we should be able to give a (sequence of) instructions having the equivalent
effect on %aBrand Y%*. In this manner we can change the code generators in %3compile%*
to generate code to run on %aBrand Y%*. We thus would have a %3compile%* function,
call it %3compile*%*, running on %aX%* and producing code for %aY%*.
Now if we take the Sexpr forms of %3eval, apply, read, print, compile,...%* etc.
and pass these functions through %3compile*%*, we will get a large segment
of a LISP system which will run on %aY%*. Certain primitives will have to be
supplied to run this code on %aY%*, but a very large part of LISP can be
bootstrapped from %aX%* to %aY%*.
Obviously, before we can use %2a%* compiled version of the compiler (or
in fact, before we can use any compiled code) we must have some means of
translating the list output of the compile function into real instructions in the
machine. So if the version of LISP which we are implementing is to have a
compiler we must allocate an area of memory which can receive the compiled code.
This area is usually called %2⊗→Binary Program Space↔←%* (BPS). The translation program
which takes the list of output from the compiler and converts it onto actual
machine instructions for ⊗→BPS↔← is called an assembler. Before discussing ⊗→assemblers↔←
we will examine a sequence of simple compilers corresponding to the LISP
subsets evaluated by ⊗→%3tgmoaf%*↔←, ⊗→%3tgmoafr%*↔← and finally an ⊗→%3eval%*↔← which
handles local variables.
.SS(Compilers for subsets of LISP)
We will examine compilers for increasingly complex subsets of LISP
beginning with functions, composition and constant arguments and
ending with a more realistic compiler for a reasonable subset of
pure LISP. Though each subset is a simple extension of its predecessor,
each subset introduces a new problem to be solved by the compiling algorithm.
If the corresponding evaluator (⊗→%3tgmoaf%*↔←, ⊗→%3tgmoafr%*↔← and the most
simple ⊗→%3eval%*↔←) is well understood, then the necessary steps
to be added to the compiler are easy to make.
First we need to begin describing a list of conventions which will remain in
effect through out this sequence of compilers. The code which is generated
must be compatible with that which incorporates the basic LISP machine.
In particular the calling conventions for function invocation must be
maintained. Thus a function of %3n%* arguments expects its arguments to
be presented in AC1 through ACn. Also the execution of any code which is
computing arguments to a function call must store temporary results on the stack,
%3P%*. Thus the execution sequence of code for computing %3n%* arguments
should be:
.BEGIN centerit;
←compute value of argument%41%*, push onto stack, %3P%*.
←..........
←compute value of argument%4n%*, push onto stack, %3P%*.
.END
So after this computation the values of the arguments are stored
V%4n%*, V%4n-1%*, ..., V%41%*, from top to bottom in %3P%*.
Thus to complete the function invocation, we need only pop the arguments
into the AC's in to obvious order. This brings us to the last
(and the most important!) convention for the initial compiler.
We must always be sure that the integrity of the stack is maintained. What ever
we push onto the stack within the body of a function %6must%* be
popped off before we exit from the function body. That is, the state of the stack
must be transparent to any computations which occur within the function.
The first compiler will handle (the S-expression translation of) that
subset of LISP forms defined by the following BNF equations:
.BEGIN TABIT1(11);GROUP
<form>\::= <constant> | <function>[<arg>; ...; <arg>] | <function> [ ]
<arg>\::= <form>
<constant>\::= <sexpr>
<function>\::= <identifier>
.END
This LISP subset corresponds closely with ⊗→%3tgmoaf%*↔←, handling only
function names, composition, and constant arguments.
Our previous compiling conventions will keep us in good stead.
We need only consider the compilation of constants. A S-expression
constant will be seen as %3(QUOTE ...)%* by the compiler. The
code which we wish to generate is:
.BEGIN TABIT1(30);SELECT 3;GROUP
\(MOVEI AC1 (QUOTE ...))
.END
It should now be clear how to proceed with the first compiler.
.BEGIN SELECT 3;TABIT2(11,18);
.GROUP
compexp <=\λ[[exp]\[eq[car[exp];QUOTE] → list[list[MOVEI;AC1;exp]];
\\ T → compapply[car[exp];complis[cdr[exp]];length[cdr[exp]]]] ]
.APART
.GROUP
complis <=\λ[[u]\[null[u] → NIL;
\\ T → append[compexp[car[u]];((PUSH P AC1));complis[cdr[u]]]] ]
.APART
.P82:
compapply <= λ[[fn;args;n]append[args;loadac[n];list[list[CALL;n;list[E;fn]]]]]
.APART
.P56:
.GROUP
loadac <=\λ[m]\[zerop[m] → NIL;
\\ T → cons[list[POP;P;cdr[assoc[n;aclist]]];loadac[n-1]] ]
%1where:%* aclist %1is%* ((1 . AC1) ... (N . ACn)).
.END
Notice that the actual function call generated by %3compapply%* is of the
form:
←%3(CALL%* n%3(E%* name%3))%1
The %3E%*-construct is discussed in the next section on assembling.
The code generate by this compiler is clearly inefficient, but that
is not the point. We wish to establish a correct compiler, then later
worry about efficiency.
The innovation which occurred in %3tgmoafr%* was the apprearance of conditional
expressions. To describe conditional expressions, the above BNF equations
were augmented by:
←<form> ::= [<form> → <form> ; ... <form> → <form>]
Certainly the addition of conditional expressions will mean an extra
piece of code in %3compexp%*
to recognize %3COND%* and a new function (analogous to %3evcond%* in %3tgmoafr%*)
to generate the code for the %3COND%*-body.
In fact, the only difference between %3evcond%* and its counterpart in
%3compexp%*, which we shall call %3comcond%*, is that %3comcond%* generates
code which when executed will produce the same value as the value
produced by %3evcond%* operating on the given S-expression.
The effect of %3comcond%* on a conditional of the form:
(%2*1*%*)←%3(COND (%1p%41%* e%41%3) ... (%1p%4n%* e%4n%3))%1 should be clear.
First generate code for p%41%*; generate a test for truth, going to the
code for e%41%* if true, and going to the code for p%42%* if not true.
The code for e%41%* must be followed by an exit from the code for the
conditional, and we should probably generate an error condition to be executed
in the case that p%4n%* is false.
.BEGIN NOFILL;GROUP;
Pictorially, we might represent the code as:
<code for p%41%*>
T NIL
<code for e%41%*> <code for p%42%*>
T NIL
<code for e%42%*> <code for p%43%*>
.... ....
T NIL
<code for e%4n%*> <code for error>
.END
This requires the establishment of more conventions for our compiler.
In particular we must be able to test for %3T%* (or %3NIL%*). We will
define %3NIL%* to be the zero of the machine, and we will test for
%3NIL%* using the %3JUMPE%* instruction
(see {yonss(P33)}). Next, since our code is to be a %2sequence%* of instructions,
we must linearize this graph representation of the generated code.
Thus for the compilation of *1*, above,
we will generate:
.BEGIN TABIT2(30,35);GROUP
\%3(\%1<code for p%41%*>%3
\\(JUMPE AC1, L1)%1
\\<code for e%41%*>%3
\\(JRST L)
\L1\%1<code for p%42%*>%3
\\(JUMPE AC1, L2)
\ ...
\Ln-1\%1<code for p%4n%*>%3
\\(JUMPE AC1, Ln)%1
\\<code for e%4n%*>%3
\\(JRST L)
\Ln\(JRST ERROR)
\L\ )
.END
%1
To generate such code we need to be able to generate the labels, %3Li%*.
The generated labels should be atomic and should be distinct. LISP has
a function, ⊗→%3gensym%*↔←, which can be used for this task. %3gensym%*
is a function of no arguments whose value is a generated symbol or atom
which is guaranteed to be distinct from any atom generated in any of
the usual manners. In many versions of LISP, gensyms are of the form
%3Gn%* where %3n%* is a four digit number beginning at %30000%*. Thus
the first call; %3gensym[ ]%* would give %3G0000%*; succeeding calls would give
%3G0001, G0002%*, etc.
First, gensyms are not placed in the object list since
they are usually used only for their unique name. Second, if you explicitly
place them in the symbol table they are obviously distinct from each other and
will be distinct from all other atoms unless, of course, you read in such an atom.
Without too much difficulty we can now add the recognizer for
%3COND%* to %3compexp%* and construct %3comcond%*.
.BEGIN SELECT 3; TABIT3(27,34,45);TURN OFF"←";GROUP;
.FILL
%1Add%* eq[car[exp];COND] → comcond[cdr[exp];gensym[ ]]; %1to%3 compexp
%1where:
.NOFILL
%3
comcond <= λ[[u;l][prog[[z]\z ← gensym[ ];
\return[\[null [u] → list[(JRST ERROR);l]:
\\ T → append\[compexp[caar[u]];
\\\ list[list[JUMPE;AC1;z]];
\\\ compexp[cadar[u]];
\\\ list[list[JRST;l]z];
\\\ comcond[cdr[u];l]]]]
.END
%1
.BEGIN GROUP;TABIT2(30,38);
The partially exposed recursive structure of %3comcond%* would show:
←%3comcond[((%1p%41%* e%41%3) ...(%1p%4n%* e%4n%3));G0000]=
\%3(%1\<code for p%41%*>%3
\\(JUMPE AC1, G0001)%1
\\<code for e%41%*>%3
\\(JRST G0000)
\ G0001\comcond[((%1p%42%* e%42%3) ...(%1p%4n%* e%4n%3))])
.END
%1
So the second argument to %3comcond%* is a generated symbol to reflect the
label attached to the end of the conditional statement. There is
another generated name used "locally" to %3JUMPE%* from p%4i%* to
p%4i+1%*.
Before attacking the major problem of our compilers, the handling of
variables, we shall describe how the list representing the output
of the compiler is turned into code which runs on the machine.
.SS(Problems)
.BEGIN TABIT1(16);
I. Evaluate:
%3compexp[(COND(\(EQ (QUOTE A)(QUOTE B))(QUOTE C))
\((NULL (QUOTE A))(QUOTE FOO))))]
****more, more ****
.END
.SS(One-pass Assemblers,assemblers,P7:)
Define %3compile%* as:
%3compile <= λ[[fn;vars;exp]append[list[list[LAP;fn;SUBR]];compexp[exp]]]%*.
Consider the output from %3compile%* for the function:
.GROUP
%3←j [] <= f[g[A];h[B]]%*
or more precisely, for the evaluation of
←%3compile[J;();(F(G(QUOTE A))(H(QUOTE B)))]%*.
.APART
.GROUP
It would be a list of the form:
.BEGIN TABIT2(10,45);SELECT 3;
\((LAP J SUBR)\%1; says %3j%* is a function%3
\(MOVEI AC1(QUOTE A))\%1; make argument for call on %3g
\(CALL 1 (E G))\%1; call the function%3
\(PUSH P AC1)\%1; save the value%3
\(MOVE AC1(QUOTE B))
\(CALL 1 (E H))
\(PUSH P AC1)
\(POP P AC2)
\(POP P AC1)
\(CALL 2(E F))
\(POPJ P)
\)
.END
.APART
%1
As you know the machine representation of these instructions are encodings of
specific fields of specific machine locations with specific numbers.
For example, the operation %3PUSH%* is represented as a certain number,
called its %2⊗→operation code↔←%* or %2op code%*, and which will
occupy a certain area of a machine word so that the CPU can interpret
it as an instruction to push something onto a stack. Other fields in the
instruction are to be interpreted as references to stacks, to memory locations,
to accumulators, constnats or external references to other routines.
The purpose of an assembler is to translate these mnemonic instructions
into raw seething machine instructions.
Essentially all that the assembler need do is search ⊗→symbol tables↔←
for the opcodes, for subroutine names, for accumulator and stack names,
and store the resulting values in the appropriate machine locations.
Things are slightly more complex: we must also %6add%* information to
the tables as we proceed. For example, as we assemble the code for a new
routine we must add its name and starting address to the current symbol
table. The phrase, %3 (LAP %1name%3 SUBR)%* does this.
We must exercise a bit of care in handling %3QUOTE%*d expressions.
Assembling a construct like %3(MOVEI AC1 (QUOTE (A B C)))%* should
have the effect of constructing the list %3(A B C)%* in free space
and placing an instruction in memory to load the address of this list into AC1.
What we must notice is that this list %3(A B C)%* is subject to
garbage collection and, if left unprotected, could be destroyed.
There are a couple of solutions. Perhaps the garbage collector could
look through compiled code for any references to free- or full-word- space;
or we could make a list of all of these constants and let the garbage
collector mark the list.
Much more problematic is the handling of labels and references to labels.
This case arose in the compiler for ⊗→%3tgmoafr%*↔← when we introduced
conditional expressions. Recall that the code for a ⊗→conditional expression↔←
of the form:
.GROUP
%3←(COND (%1p%41%* e%41%3) ... (%1p%4n%* e%4n%3)) %1 was:
.BEGIN TABIT1(35);
\ <code for p%41%*>
\ %3(JUMPE AC1 L1)%1
\ <code for e%41%*>
\ %3(JRST L)
\L1 %1<code for p%42%*>
\ %3(JUMPE AC1 L2)%1
\ ....
\ <code for e%4n%*>
\%3L ....
.END
.APART
%1
The symbols, %3 L, L1,%* and %3L2%* in this example are labels. Notice
that if we were to consider writing the assembler in LISP,
we could distinguish occurrences of labels from instructions using
the predicate, %3atom%*.
It perhaps is time to start thinking about writing such an assembler.
One of the arguments to the function should be the list representation
of the program. One of its arguments should also describe where (in ⊗→BPS↔←)
we wish the assembled code to be located. We should also have access
to an initial symbol table, describing the opcodes and pre-defined
symbol names. Let's call the function, ⊗→%3assemble%*↔←.
%3assemble%* then can go %3cdr%*-ing down the program list, looking up
definitions and manufacturing the numerical equivalent of each
instruction, then depositing that number in the appropriate machine
location. If %3assemble%* comes across a label definition, it should
add information to a symbol table, reflecting that the label has
been seen and that it is associated with a specific location in memory.
Then future references to that label can be translated to references
to the associated machine location. The only problem is that references
to labels may occur %6before%* we have come across the label definition
in the program. Such references are called %2⊗→forward reference↔←s%*.
.GROUP
For example, consider the following nonsense program:
.BEGIN TABIT1(35);SELECT 3;
\( (LAP FOO SUBR)
\ X (JRST X)
\ (JRST Y)
\ Y (JRST X) )
.END
.APART
The reference to %3Y%* is a forward reference; neither of the references to %3X%*
is forward since %3X%* is defined before being referenced.
There are two solutions to the ⊗→forward reference↔← problem:
.BEGIN INDENT 0,5;
%21.%* Make two passes through the input program. The first pass
decides where the labels will be assigned in memory. That is, this
pass builds a symbol table of labels and locations. Then a second pass
uses this symbol table to actually assemble the code into the machine.
This works, but is not particularly elegant. It is expensive to read through
the input twice, particularly when we can do better.
%22.%* The other solution is to make one clever pass through the input.
Whenever we come across a forward reference we add information to the symbol table
telling that a forward reference has occurred at this location. We assemble
as much of the instruction as we can. When a label definition %6does%*
occur we check the table to see if there are any forward references pending
on that label. It there are such we %6⊗→fix-up↔←%* those instructions to
reference the location now assigned to the label.
.END
A speed-up by a factor ranging from two to five is not uncommon for a good
one pass assembler.
There are some restrictions which are imposed on one-pass assemblers, but
particularly for assembling compiled code, one-pass assemblers are quite sufficient.
There are at least two ways to handle fixups and forward references. If
the fixups are of a particularly simple nature, say only requiring fixups
to the address-part of a word, then we may link those pending forward references
together, chaining them on their address parts. Thus:
.GROUP SKIP 20;
Another solution, which is potentially more general (that is, it could
handle left-half, right-half or partial-word fixups) is to store the information
about each fixup in the symbol table under each label. Thus:
.GROUP SKIP 20;
Both methods are useful. Both have been used extensively in assemblers and
compilers.
To write the function, %3assemble%*, we will need two functions:
.BEGIN INDENT 0,10;
%21.%* ⊗→%3deposit%*↔←%3[x;y]%*: %3x%* represents a machine address; %3y%* is a list,
representing the instruction to be deposited. %3y%* should be a list of
four elements: %3(%*opcode ,accumulator number, memory address, index register%3)%*
The value of %3deposit%* is the value of %3y%*.
%22.%* ⊗→%3examine%*↔←%3[x]%*: %3x%* represents a machine address. The value
of %3examine%* is the contents of location %3x%* in the form of a list as
specified above.
.END
.BEGIN TURN ON "#";
%3assemble%* needs to recognize that there are different instruction formats.
That is,some instructions use an opcode and a memory reference: %3(JRST#L)%*;
some use an opcode, accumulator, and an address: %3(PUSH#P#AC1)%*; and some
vary: %3(MOVE#AC1#(QUOTE A))%* and %3(MOVE#AC1#-1#P)%*. %3assemble%* also
has to have an initial symbol table of opcodes, accumulator numbers, and
stack numbers:
.END
.BEGIN TABIT2(35,45);GROUP;
%2\symbol\value%3
\MOVE\200
\MOVEI\201
\SUB\274
\JRST\254
\JUMPE\322
\JUMPN\326
\PUSH\261
\POP\262
\POPJ\263
\CALL\034
\AC1-n\1 - n
\P\14
.END
.GROUP
So for example:
←%3assemble[((LAP FOO SUBR) X (JRST X) (JRST Y) Y (JRST X));104]%* should
have the final effect:
.BEGIN TABIT1(43);
--→%7α~~~]%*--→%bPNAME%7[~~[~~]%1--→%7[~~]~~]%*--→%bSUBR%7[~~[~~]%1...
\|
\|
\|
\| op ac ind add
\→104 254 0 0 104
\ 105 254 0 0 106
\ 106 254 0 0 104
.END
.APART
.SS(A compiler for simple %3eval%*,compiler,P32:)
Consider the function defined by:
←%3j[x;y] <= f[g[x];h[y]]%*
We claim that the following code suffices for function:
.BEGIN TABIT2(10,45);SELECT 3;
\(LAP J SUBR)\%1; says %3j%* is a function%3
\(PUSH P AC1)\%1; save the input args%3
\(PUSH P AC2)
\(MOVE AC1 -1 P)\%1; get %3x
\(CALL 1 (E G))\%1; call the function named %3g
\(PUSH P AC1)\%1; save the value%3
\(MOVE AC1 -1 P)\%1; get y%3
\(CALL 1(E H))\%1; call %3h
\(PUSH P AC1)
\(POP P AC2)\%1; restore the arguments in%3
\(POP P AC1)\%1; preparation for%3
\(CALL 2(E F))\%1; calling %3f
\(SUB P(C 0 0 2 2))\; %1sync the stack; remove the saved args%3
\(POPJ P)\; %1exit.%3 AC1%* still has the value from %3f.
\ )
.END
Here is a picture of the execution of the code:
.BEGIN TURN ON "\";NOFILL;TABS 5,10,25,30,45,50,65,70;SELECT 3;GROUP;
AC1: x ; AC2: y
\|\| (PUSH P AC1)\\ (PUSH P AC2)\| y\|(MOVE AC1 -1 P)\| y | (CALL 1 (E G))
\|\| =>\| x\| =>\| x\| =>\| x | =>
AC1: g[x] ; AC2: ?\\\AC1: y ; AC2: ?
\\ (PUSH P AC1)\|g[x]\|(MOVE AC1 -1 P)\|g[x]\| (CALL 1(E H))
\| y\| =>\| y\| =>\| y\| =>
\| x\|\| x\|\| x\|
AC1: h[y] ; AC2: ?\\\AC2: h[y]\AC1: g[x] ; AC2: h[y]
\|g[x]\| (PUSH P AC1)\|h[y]\| (POP P AC2)\|g[x]\| (POP P AC1)\| y |(CALL 2 (E F))
\| y\| =>\|g[x]\| =>\| y\| =>\| x | =>
\| x\|\| y\|\| x\|
\ \ \| x\|
AC1: f[g[x];h[y]]
\| y\|(SUB P (C 0 0 2 2))\\|\| (POPJ P)
\| x\| => \=>
.END
.BEGIN INDENT 0,10;TURN ON "#";
Notes: The %3(MOVE %*x -n%3 P)%1 instruction allows us to put a copy
of the contents of the n%8th%* element down the stack. Notice too, that
the addressing in the code is relative to the top of the stack: %3(MOVE#AC1#-1#P)%*
gets us %3x%* in one instance and gets us %3y%* in another, because the top
of the stack changes.
.END
Clearly we want a compiler to produce equivalent (albeit inefficient) code.
Once we understand how to do this it is relatively easy to improve on the efficiency.
We shall now extend %3compile%* to handle local variables.
.<<discussion of offset and vpl>>
.BEGIN TURN ON "#";
The major failing of the previous %3compile%* is its total lack of
interest in variables. This is a non-trivial problem which every
compiler must face. You have just seen an example of plausible code
generation for simple LISP functions, in particular:
←%3j[x;y] = f[g[x];h[y]]%*
The crucial point is how to generate code which `knows'
where on the stack we can find the value of a (local) variable when
we execute that code. What we shall do is simulate the behavior of
the runtime stack while we are compiling the code. The compiler
cannot know what the %2values%* of the variables will be at runtime but
we claim that it should know %3where%* to find the values. We will carry
this information through the compiler in a manner reminiscent of the
`dotted-pair' symbol table of the first version of %3eval%* seen in {yonss(P6)}. Instead of
posting the current values in the stack, the compiler will post information about the
positions of the variables relative to the top of the stack at the
time we enter the function. The variable %3vpl%*, for variable pair list,
contains this information. That is if we are
to compile a function with λ-variables, %3[x;y;z]%* then %3vpl%* will begin
with:
←%3((X . 1), (Y . 2), (Z .3) ...%*
When we set up %3vpl%*
we also set the %2⊗→offset↔←%*, called %3m%*, to minus the number of args added
to %3vpl%*. (In this case -3). Now if we come across a reference say to
%3Y%* while compiling code, we use %3cdr[assoc[Y;vpl]]%* to retrieve %32%*. The
offset plus this retrieved value gives us the relative position of %3Y%*
in the stack. I. e., -3 + 2 = -1. Thus to refer to the stack
location of %3Y%* we could use %3(....-1#,#P)%*. What happens as we add
elements to the stack? (Or to be more precise...what happens as we
generate code which when executed will add elements to the stack.)
Clearly we must modify the offset. If we add one element, we would
set %3m%* to -4. Then to reference %3Y%* now use -4 + 2 = -2. I. e. a
reference to %3Y%* is now of the form:
←%3( ......-2 P).%*
But that's right. %3Y%* is now further down in the run time stack. So
to complete the analogy, the `symbol table' is really defined by %3m%*
plus the current %3vpl%*.
When will the compiler make modifications to the top of the stack? First, we
push new elements when we are compiling the arguments to a function
call. The function in the new compiler which compiles the argument
list is called %3complis%*:
.BEGIN SELECT 3; TABIT2(22,32);GROUP
complis <= λ[[u;m;vpl]\[null [u] → NIL
\ T → append\[compexp [car [u]; m; vpl];
\\ ((PUSH P AC1));
\\ complis [cdr [u]; m-1; vpl]]]
.END
Notice that %3complis%* compiles the arguments from left to right,
interspursing them with %3(PUSH#P#AC1)%* and recurring with a new offset
reflecting the effect of the %3PUSH%*. Clearly this function is analogous to
%3evlis%*.
Here's a brief description of the parts of the new compiler. This compiler was
adapted from one written
by John McCarthy in conjunction with a course at Stanford University
entitled %3Computing with Symbolic Expressions%*. The McCarthy compiler
was also the subject of study by Ralph London in his paper,
%3Correctness of Two Compilers for a LISP Subset%*.
.BEGIN INDENT 0,15;
%3compile[fn;vars;exp]: fn%* is the name of the function to be compiled. %3vars%* is the
list of lambda variables. %3exp%* is the lambda-body.
%3prup[vars;n]: vars%* is a lambda list, %3n%* is an integer. %3prup%* builds a
variable-pair list.
%3mkpush[n;m]%*: generates a sequence of %3PUSH%* instructions.
%3loadac[n;k]%*: is a slight modification of the previous %3loadac%* ({yon(P56)}).
This version generates a series of %3(MOVE ACi ...)%* instructions followed
by a %3(SUB P (C 0 0 N N))%*, rather than a sequence of %3POP%*s.
%3compexp[exp;m;vpl]%*: this function does most of the work. It is analogous to
%3eval%*.
It generates the code for constants,
for a reference to a variable,
and for conditional expressions.
It is used for compiling code for a call on a function,
compiling the argument list with %3complis%*, which will
leave the arguments in the stack; %3loadac%* loads the appropriate %3AC%*'s.
and then we generate the %3SUB%* to sync the stack, and finally generate
a call on the function.
%3comcond[u;m;l;vpl]%*: this compiles the body of conditional expressions. %3u%* is the
p%4i%* - e%4i%* list; %3l%* will be bound to a generated symbol name
; %3m%* and %3vpl%* are as always.
.END
.END
Fortified by the previous %3compile%* functions and this introduction
the new %3compile%* should be clear.
.BEGIN NOFILL ;select 3;TURN OFF "←";
.GROUP
compile <= λ[[fn;vars;exp]
prog[[n]
n ← length [vars];
return [append [list[list [LAP;fn;SUBR]];
mkpush [n;1];
compexp [exp; -n; prup [vars;1]]
list [list [SUB;P;list [C;0;0;n;n]]]
((POPJ P)) ]]]
.APART
.GROUP
prup <= λ[[vars;n]
[null [vars] → NIL;
T → cons [cons [car [vars]; n]; prup [cdr [vars];n+1]]]
mkpush <= λ[[n;m]
[lessp [n;m] → NIL
T → cons [list [PUSH;P;cdr[assoc[m;aclist]]]; mkpush [n;m+1]]]
.APART
.GROUP
loadac <= λ[[n;k]
[greaterp[n;0] → NIL;
T → cons[list[MOVE;cdr[assoc[k;aclist]];n;P];loadac[n+1;k+1]]]]
.APART
.GROUP
compexp <= λ[[exp;m;vpl]
[null [exp] → ((MOVEI AC1 0));
or [eq [exp;T]; numberp [exp]] → list [list [MOVEI;AC1;list [QUOTE; exp]]];
atom [exp] → list [list [MOVE;AC1;m + cdr [assoc [exp;vpl]]; P]];
eq [car [exp]; COND] → comcond [cdr [exp]; m; gensym [ ]; vpl];
eq [car [exp]; QUOTE] → list [list [MOVEI;AC1;exp]];
eq [atom [car [exp]] → λ[[n]append [complis [cdr [exp];m;vpl]
loadac [1-n;1];
⊗↓%1This is sufficiently mysterious to warrant explanation.
The "%3λ[[n]#...#][length[cdr[exp]] %*" is an internal λ-expression
of one argument,
analogous to the call on %3compapply%* in the first compiler ({yon(P82)}).←%3
list [list [SUB;P;list [C;0;0;n;n]]
list [list [CALL;n;
list [E; car [exp]]]]]
[length [cdr [exp]]]]]
.APART
.GROUP
comcond <= λ[[u;m;l;vpl]
[null [u] → list[l];
T → λ[[l1] append [comexp [caar [u];m;vpl];
list [list[JUMPE;AC1;l]];
⊗↓%1The same trickery used here as in %3compexp%*: %3l1%* is bound
to the value of %3gensym[ ].%1←%3
compexp [cadar [u];m;vpl];
list [list [JRST;l];l1]
comcond [cdr [u];m;l;vpl]]]
gensym [ ]]
.APART
.END
Here is a partial sketch of %3compile%* operating on %3j <= λ[[x;y]f[g[x];h[y]]].%*
.BEGIN SELECT 3;TABIT2(10,17);CENTERIT;
.GROUP
compile[J;(X Y);(F (G X) (H Y))] %1gives:%*
\append\[((LAP J SUBR)); (**1**)
\\ mkpush[2;1];
\\ compexp[(F (G X)(H Y));-2;prup[(X Y);1]];
\\ (SUB P (C 0 0 2 2))
\\ ((POPJ P ))];%1
.APART
.GROUP
where:
←%3mkpush[2;1]%* gives %3((PUSH P AC2)(PUSH P AC1)),%* and
←%3prup[(X Y);1]%* gives %3((X . 1)(Y . 2))%*.
.APART
.GROUP
%3compexp[(F (G X)(H Y));-2;((X . 1)(Y . 2))]%* results in:
%3
\append\[complis[((G X)(H Y));-2;((X . 1)(Y . 2))];
\\loadac[-1;1];
\\((SUB P (C 0 0 2 2)));
\\((CALL 2(E F)))]
%1and %3loadac[-1;1]%* evaluates to: %3((MOVE AC1 -1 P)(MOVE AC2 0 P))%*.
.APART
.GROUP
Thus (**1) above, is of the form:
%3
\\((LAP J SUBR)
\\ (PUSH P AC2)
\\ (PUSH P AC1)
\\ complis[((G X)(H Y));-2;((X . 1)(Y . 2))]
\\ (MOVE AC1 -1 P)
\\ (MOVE AC2 0 P)
\\ (CALL 2 ( E F))
\\ (SUB P (C 0 0 2 2))
\\ (POPJ P)
\\)
.APART
.FILL;
%3complis%1 is interesting since it actually uses the %3vpl%* we have been
carrying along. It gives rise to:
.NOFILL
.GROUP
%3
\append\[compexp[(G X);-2;((X . 1)(Y . 2))];
\\ ((PUSH P AC1));
\\ complis[((H Y));-3;((X . 1)(Y . 2))]]
.APART
.GROUP
%1and the %3compexp%* computation involves, in part:
%3
\append[complis[(X);-2;((X . 1)(Y . 2))];
\\ ((MOVE AC1 0 P));
\\ ((SUB P (C 0 0 1 1));
\\ ((CALL 1 (E G))]
.APART
.GROUP
%1Finally this %3complis%* generates the long awaited variable reference using:
%3compexp[X;-2;((X . 1)(Y . 2))] %1giving,
\\%3((MOVE AC1 -1 P))%*.
.APART
Notice that the offset is different within the call:
←%3 complis[((H Y));-3;((X . 1)(Y . 2))].%1
Finally, you should convince yourself that the code, though inefficient, is correct.
.END
.APART
←%2Problems%*
I Simple problems
1. Evaluate %3compile[%1 h.s.]
etc.
2. Complete the code generation for the above example.
.SS(A project: Efficient compilation)
.P35:
Certainly the most striking feature of the last %3compile%* is its
outrageous inefficiency. Examination of the compilation of the
most simple function suggests many possible improvements.
We should first clarify what we mean the efficiency in this context.
We might mean minimal compile-time. In this case we would want a very
simple compiler; this usually means that the complied code is extraordinarily
bad. Such compilers might suffice for debugging runs or student projects.
More likely, efficiency compilation is taken to mean production of
code which we could expect from a reasonably bright machine-language programmer.
It should run reasonably fast, not have obviously redundant instructions, and
not take too much space in the machine. It is this second interpretation
of efficiency which we shall use.
A major inefficiency occurs in saving and restoring quantities on the
stack. For example, the sequence %3(PUSH P AC1)(POP P AC1)%* serves no
useful purpose. This is a symptom of a more serious disease.
The compiler does not remember what will be in the ACs at run-time. Since the
arguments to a function call must be passed through the special AC registers
and since it is expensive to save and restore these registers, we should
make a concerted effort to remember what quantities are in which ACs and
not reload them unnecessarily. This process will certainly make the
compiler more complicated and that will mean longer compilation time but
compilation usually occurs less frequently than execution of compiled
code.
Here are some possibilities.
****ADD 'EM*****
diatribe about go to
A major obstacle to this kind of optimization is the unrestricted use
of labels and gotos. Consider a piece of compiler code which has a label attached
to it.
Before we can be assured of the integrity of an AC
we must ascertain that every possible path to that label maintains that AC.
This is a very difficult task. The label and goto structure required by
%3compile%* is quite simple. However if we wished to build a compiler for
LISP wirh %3prog%*s we would have to confront this problem.
.SS(A project: One-pass assembler)
.P10:
III A one-pass ⊗→assembler↔←.
Write a one-pass assembler for the code generated by the %3compile%* function
of this section. You should be aware of the following points:
.BEGIN INDENT 0,5;
%2a.%* %3QUOTE%*d expressions must be protected from garbage collection. The
simplest way to accomplish this it to save them on a list, say %3QLIST%*.
%2b.%* Use the operation codes of {yonss(P7)})
****MORE ON INST FORMAT.***
%2c.%* Design a simple fixup scheme. Notice that %3compile%*'s code will
require address fixups at most.
%2d.%* Recall that the format of the code is a list. The items in the list are
either atomic -- representing labels --, or lists -- representing instructions--.
The instructions have varying format. Perhaps a ⊗→table-driven↔← scheme can be used.
%2e.%* Some attempt should be made to generate error messages.
%2f.%* Many of the constants, %3(C 0 0 %*n n%3)%*, occur frequently; these constants
are only referenced, never changed by execution of the compiled code. Write
your assembler to maintain only one copy of each. The constants should be stored
directly after the compiled code.
%2f%*. Try to be equally clever about storing %3QUOTE%*d expressions.
.P36:
IV ***problem on internal lambdas
.END
.SS(A project: Syntax directed compilation,syntax-directed,P4:)
compilation for sae
BNF for mexprs
syntax directed compiler
scanner parser
.SS(A deep-binding compiler,deep binding)
**sketch of tgmoaf deep binder conventions
**project: do tgmoafr and eval d-b compr
**hints about globals and name stack
**project: do eval compiler using name-value stack for locals.
.SS(Compilation and global variables,global variables,P5:)
.BEGIN TURN ON "#";
**** expand greatly***
The models of compilation which we have sketched so far store
their λ-variables in the stack, %3P%*. References to those
variables in the body of the λ-expression are made to those
stack entries. This scheme suffices only for lambda or %3prog%* (local)
variables. We have said that λ-expressions may refer to global
or free variables. The lookup mechanism simply finds the current
binding of that global in the symbol table. Notice that this is a
different strategy than the global lookup of Algol. In Algol, when a
procedure refers to a global we take the binding which was current at
the point of definition of the procedure. The LISP mechanism is
called %2⊗→dynamic binding↔←%*. It corresponds to physically substituting
the body of the definition of the function wherever it is called.
Its model of implementation is simpler than that required for Algol.
We don't need the ⊗→static chain↔← for this case of global lookup. Thus
interpreted expressions encounter no problems when faced with global
variables. There are potential difficulties for compiled code. If
all we store of the stack in a compiled function is the value of a
variable then another program which expects to use that variable
globally will have no way of finding that stored value. One scheme
is to store pairs on the stack: name and value (LISP#1.85) then we
can search the stack for the latest binding. It works. With this
scheme we can dispense with the ⊗→%3VALUE%*-cell↔←. Actually this scheme
isn't all that bad. The compiler can still `know' where all the
local variables are on the stack and can be a bit clever about
searching for the globals. Notice this is the old symbol table
mechanism (⊗→a-list↔←) again. LISP#1.85 was designed for a paging
machine (XDS#940) and a few unpleasant features crept in because of
this. (However, on the positive side some nice coding tricks to
minimize page references also arose.)
The solution proposed by the LISP 1.6 implementation called
%2⊗→shallow binding↔←%*, allows the compiled code to directly access the
%3VALUE%*-cell in the symbol table. There is an artifact in the compiler
(and assembler) called %3SPECIAL%*. Variables which are to be used
globally are declared ⊗→special variables↔←. When a variable, say %3x%*, is
declared special the compiler will emit a reference to %3x%* as
%3(MOVE#AC%4i%*#(SPECIAL#X))%1
or %3(MOVEM#AC%4i%*#(SPECIAL#X))%1 rather than the corresponding
reference to a location on the stack. When the LISP assembler sees
the indicator %3SPECIAL%*, it will search the symbol table for the %3VALUE%*-cell
of %3X%* and assemble a reference to that cell. Since the location
of the value cell does %2not%* change, we can always find the current
binding posted in the %3cdr%*-part of that cell. Notice too that any
interpreted function can also sample the %3VALUE%*-cell so global values
can be passed between compiled and interpreted functions. The values
of local variables are still posted on the stack.
This then is the reason for depressing the actual value one level.
****pic
.GROUP SKIP 6;
We have not yet discussed the mechanism which will allow us
to pass back and forth between compiled and interpreted functions.
To complete that discussion we must introduce the %aSM%* instruction for
calling a function:
.BEGIN TABIT1(19);TURN OFF"←";
PUSHJ P fn\%3C%*(P) ← %aPC%*
\P ← %3C%*(P) + 1
\%aPC%* ← fn. This is called the "push-jump" instruction. Exit with POPJ.
.END
First we
require that the calling conventions for both kinds of functions be
isomorphic.
When an interpreted function calls a compiled (or primitive)
function, %3eval%* will look for the indicator, %3SUBR%*; then retrieve the
machine address of the code and enter via a %3PUSHJ%*. That code should exit
(back to %3eval%*) via a %3POPJ%*, after assuring that the stack, P, has
been restored to the state at the time of entry.
Compiled functions call other functions via the %3(CALL#%1n%*#(E#%1fn%3))%1
artifact. The %3CALL%* opcode is actually an illegal instruction
which is trapped to a submonitor inside %3eval%*. This submonitor looks
down the property list of the atom, fn, for a function indicator
(%3SUBR, EXPR%*, etc). The function is called and control is then
returned to the address immediately following the %3CALL%*. In many
cases this %3CALL%* can be replaced by a %3(PUSHJ#P#%1fn%3)%*, but not always as
we will see next.
.END
.SS(Functional Arguments,,P3:)
***more h.s.***
***farting with funarg***
funarg b-w. and weizen
**add deep-binding compiler**
what does this say about the CALL mechanism in the compiler? It says that
the calling mechanism for a functional argument must always be
trapped the submonitor and decoded. We cannot replace that call with
a PUSHJ to some machine language code for the function because the
function referred to can change. We actually use a CALLF instruction
to designate a call on a functional argument.
.SS(Tracing and debugging in LISP)
When can the %3CALL%* instruction be replaced by a %3PUSHJ%*? The
%3PUSHJ%* instruction is used to call a machine language function.
Obviously if we are calling an interpreted function, (it has
indicator %3EXPR%* of %3FEXPR%*) %3PUSHJ%* is the wrong thing to do. In this
case we must pass control to %3eval%*, evaluate the function with the
appropriate arguments, return the value in %3AC1%* and finally return
control to the instruction following the %3CALL%*. If the function being
called is a machine language routine (indicator is %3SUBR%* or %3FSUBR%*)
then we could replace the %3CALL%* with a %3PUSHJ%*. This would
`short-circuit' the call on the submonitor and the calling of the
function could be done more quickly. There are many occasions in
which we do not wish to make this replacement, however.
Assume for the moment that I am mortal and that my LISP
program has some bugs. Crucial pieces of information about the
behavior of the program are: which functions are being entered, what
are the actual parameters, and what are the values being returned.
Assume that we wish to monitor the behavior of the function, %3FOO%*. We
will hide the real definition of %3FOO%* on another symbol table entry
(using %3gensym[]%*) and redefine %3FOO%* such that, when it is called, it
will:
.BEGIN narrow 10;;
%21.%* print the values of the current actual parameters.
%22.%* use %3apply%* to call the real defintion of %3FOO%* with the current parameters.
%23.%* print the value of the call on %3FOO%*.
%24.%* return control to the calling program.
.END
This device is called tracing.
Since %3FOO%* may be recursive we should also give some
indication of the depth of recursion being executed. Now every call
on %3FOO%* will give us the pertinent statistics. Interpreted calls on
%3FOO%* will go through %3eval%*, and if %3(CALL ... FOO)%* is being used in the
compiled code the submonitor can pass control to the tracing
mechanism; but if the %3CALL%* is replaced by a %3PUSHJ%*, the control passes
directly to the machine language code for %3FOO%* and we cannot intercept
the call.
On most implementations of LISP the %3PUSHJ-CALL%* mechanism is
under the control of the programmer. After the program is
sufficiently debugged, replace the %3CALL%* with the %3PUSHJ%* and the
programs will execute faster. But be warned that this action is
irreversible on most machines; once the %3CALL%*s have been overwritten it's tough beans!!
A variant of this tracing scheme can be used to monitor %3SET%*s
and %3SETQ%*s in interpreted %3prog%*s. Since calls on %3SET%* and %3SETQ%* are
interpreted (by %3eval%* and Co.), we can modify their definitions to
print the name of the variable and the new assignment, do it, and
return. (question: can you see why this perhaps won't (or shouldn't)
work for compiled code?)
This is a very brief description of debugging in LISP. It again shows
some of the power resultant from having an evaluator available at runtime.
Much more sophisticated debugging techniques
can be implemented, particularly in an on-line implementation of
LISP. Perhaps the most comprehensive on-line LISP system is INTERLISP, an
outgrowth of BBN LISP. The details of this undertaking would take us too far
afield from our current discussion.
.SS(Macros and special forms,macros,P57:)
Recall our discussion of macros and ⊗→special forms↔← in {yonss(P18)}.
We wish to extend our compiler to handle such definitions.
Consider the example of defining %3plus%* of an indefinite number of arguments
given on {yon(P58)}.
Notice first that difference in efficiency between the interpreted macro ({yon(P58)})
and the interpreted special form ({yon(P59)}) is very slight. Both require calls on %3eval%*.
One requires explicit user calls on the evaluator; one does it
within the evaluator.
In the presence of a compiler we can frequently make execution of macros
more efficient than their special form counterpart. This is the case with %3plus%*.
When %3plus%* is called we know the number of arguments, and can simply
expand the macro to a nest of calls on %3*plus%*. For example:
.begin centerit;
%3
←plus[4;add1[2];4] %1expands to%* *plus[4;*plus[add1[2];4]] %1
which can be efficiently compiled.
.end
.P73:
There is a closely related use of LISP macros which is worth mentioning.
Recall on {yon(P60)} we defined %3coef%*
as %3car%*. Compiled calls on %3coef%* would invoke the function-calling
mechanism, whereas many compilers can substitute actual hardware instructions
for calls on %3car%*, resulting in more efficient run-time code.
So for efficiency's sake it would be better to write %3car%* instead of
%3coef%*. There are two objections to this. First, %3coef%* has more
mnemonic significance the %3car%*. Second, using %3car%* we have explicitly
tied our algorithm to the representation. Both are strong
objections.
Macros can help overcome both objections. Define:
←%3coef <%4m%*= λ[[l]cons[CAR;cdr[l]]]%1.
(Recall that the whole call %3(COEF ... )%* gets bound to %3l%*.)
So the user writes %3(COEF ...)%*; the evaluator sees %3(COEF ...)%* and
finally evaluates %3(CAR ...)%*; and the compiler sees %3(COEF ...)%*
and compiles code for %3(CAR ...)%*. So we can get the efficient code, the
readibility, and flexibility of representation with macros.
Since %3eval%* handles calls on special forms, we should examine the
extensions to %3compile%* to generate such code. We have seen that
in compiling arguments to (normal) functions, we generate the code for
each, followed by code to save the result in the run-time stack, %3P%*.
The argument to a special form is %2unevaluated%*, by definition. All we
can thus do for a call of the form %3f[l]%*, where %3f%* is a special form,
is pass the argument, compiling something like:
.BEGIN CENTERIT;SELECT 3;GROUP;
←(MOVEI AC1 (QUOTE (l)))
←(CALL 1 (E F))
.END
This should also be clear from the structure of %3FEXPR%* calling in the %aSM%*
evaluator.
←%2Problems%*
I. Extend the last %3compile%* function to handle macros.
II. We have seen the (necessarily) inefficient code generated by a compiler
for %3FEXPR%* calls. Assume ⊗→%3and%*↔← is a special form with an indefinite
number of arguments. Show how to modify %3compile%* to recognize %3and%*
and compile efficient code for its execution.
.SS(Numbers,numbers)
In most implementations of LISP, numbers are stored as very simple kinds of
atoms: they do not need print names, but since we should probably
allow fixed and floating point representation, we do need indicators
for these properties. Thus:
.BEGIN TABIT2(10,45);GROUP;
\fixed-point 1\floating-point 1.0
\|\|
\|--→%7α~~]%1--→%7[%bFIXNUM%7]~~]%1--→%7[~%11%*~]\%1|--→%7α~~]%1--→%7[%bFLONUM%7]~~]%1--→%7[%1201400000000%7]
.END
Notice that each actual number is stored in FWS. This representation
is a bit expensive. On some machines we can use a coding trick to
improve representation of some numbers. Assume that the addressing
space of the machine is 2%818%* and that the usual size of a LISP
core image is significantly smaller, say, N. Then all memory address
references greater than N are illegal (and trapped by the monitor).
What we will do is use these illegal addresses to encode some of the
smaller positive and negative integers, mapping zero on the middle
address, the positive numbers to lower addresses and the negatives
onto the higher addresses. Thus these smaller integers are
represented by pointers outside of the normal LISP addressing space.
This trick can considerably decrease the storage requirements for
jobs heavily using small numbers. (Numbers are not usually stored
uniquely).
.group
.GROUP SKIP 20
%2←Picture of INUM Space%*
.apart
Most numerically oriented programs are faced at some time with
overflow. That is, they attempt to construct a number which is too
large to be represented in one machine location. There are now
several versions of LISP which will automatically change
representation when faced with overflow. This new representation
called Bignums, could have the following structure:
.group
.group skip 7;
←%2Structure of a BIGNUM%*
.apart
The value of Bignum is given by:
where α-1 is the largest number representable in one machine word.
The intertranslations between Inums, Fixnums or Flonums, and Bignums
is done automatically by %3eval%* and Co.
.SEC(Storage structures and efficiency)
Though it is true that any algorithm can be coded in terms of
manipulations of binary trees, there are many instances in which more
efficient organizations of data exist.
At the most elementary level are vectors and arrays. These
data structures could certainly be stored in a list structure format
and individual components accessed via %3car-cdr%* chains. However, most
machines have a hardware organization which can be exploited to
increase accessing efficiency over the list representation.
Similarly, strings can be represented as lists of characters. The
string processing operations are expressible as LISP algorithms. But
again this is usually not the most resonable representation. Even at
the level of list-structure operations, simple binary trees might not
be the most expeditious representation for every problem. Also many
of the algorithms we have presented in LISP are overly wasteful of
computation time. This section of notes will begin an examination of
alternatives to LISP organization. There is no best data
representation, or no best algorithm. The representations you choose
must match your machine and the problem domain you are studying. If
your application is strictly numerical then list-structure is not the
answer; if you wish to manipulate simple linear strings of characters
then list processing is too general. And there are many applications
of list processing which are sufficiently well-behaved that you don't
need a storage allocation device as complex as a garbage collector.
The point is that if you have seen the list-processing techniques in
a rich environment such as LISP and have seen the applications to
which LISP may be put, then you will be prepared to apply these
techniques in a meaningful way. Many times an (inefficient)
representation in LISP is all that is needed. You get a clean
representation with comprehensible algorithms. Once you've studied
the algorithms, efficiencies might come to mind. At that time either
recode the problem using some of the obscene LISP programming tricks
or drop into machine language if very fine control is required. Once
you have %2a%* representation it is easy to get better ones. For
example, once you have a compiler which is correct it is
easier to describe a smarter one.
This section will describe other representations than LISP binary trees
and will show some ways of increasing the efficiency of LISP programs
.SS(Bit-tables)
Bit tables: In the marking phase of a garbage collector it is
necessary to record the marking of each word. On many machines the
marking of a word is signified by setting a bit in a bit table or bit
map. For example:
.GROUP
.GROUP SKIP 8;
←%2Bit map for garbage collector%*
.apart
This might be done for several reasons. The natural choice of
setting a mark- bit in the actual word being marked may not be
possible or not the best strategy:
.BEGIN INDENT 0,6;
1. for words in FS, there is no
room if each word contains exactly two addresses; or
2. the word is
in FWS and the meaning of the information stored there would be
changed;
3. also the garbage collector must initialize all the
mark-bits to zero before the actual marking process begins (look at
the g.c. algorithm). It is faster on most machines to zero a whole
table rather than zero single bits in separate words; and finally
4. in garbage collectors for more complicated data structures, marking
with a bit table becomes a necessity.
.END
.SS(Vectors and arrays)
.BEGIN TABIT2 (10,40);CENTERIT;FILL;
%2Vectors%*: Vectors (or one dimensional arrays) are usually
stored sequentially in memory. Simple vectors are usually stored one
element to a memory location though this is not a necessity. For
example a complex vector is very naturally stored as pairs of cells;
or if perhaps you would allow vectors of non-homogeneous data modes,
each element would have to include type information. In any case,
most languages make some restrictions on the behavior of vectors such
that efficient accessing of elements can be made. There is a natural
simulation of a stack as a (sequential) vector with access to the
stack made via a global pointer to the vector.
%2Arrays%*: Arrays are multi-dimensional data structures. Since
most machine memories are linear devices we must map arrays onto a
linear representation. We will restrict attention fo the case of
two-dimensional arrays. Most of the discussion generalizes very
naturally. A very common device is to store the array by rows; that
is, each row is stored sequentially, first, row 1; then row 2,...
Given this representation there is a trivial calculation to find the
location of an arbitrary element, A[i;j], if we know the location of
the first element, A[1;1] and the extent of the dimensions of the
array. For an array A[1:M; 1:N]
←loc[A[i;j]] = loc [a[1;1]] + (i-1)*N + (j-1)
In languages like Fortran which require that the size of the array be
known at compile-time the compiler can generate the accessing code
without problem. Languages, like Algol 60, and some versions of LISP
which allow the size of an array to be determined at runtime require
a bit more care. Algol 60, for example requires that you declare the
type (real, boolean, etc.) of the array and specify the number of
dimensions in the array, but you can postpone until runtime the
designation of the size of each dimension. To handle this complexity
a dope vector is introduced. The compiler can determine the size of
the dope vector, but not the contents. The dope vector is filled in
at runtime and contains information about the actual extent of the
array bounds. Also since the size of the array is not known, the
compiler cannot allocate space for the array elements. The
allocation must be done at runtime. When the array declaration is
executed we must know all the information about the array. At that
time we add the array-bound information to the dope vector and add
information telling where to find the array elements. Assume that
the array elements are stored by rows. Look at the calculation of
the location of element, A[i;j]. For specific execution ofan array
declaration much of this information is constatnt; the location of
the array elements, in particular, A[1;1] and the number of columns,
N, is fixed. Thus we rewrite the calculation as:
\constant part\variable part
\ [loc [A[1;1]]-N-1] +\ (i*N+j)
The constant part is stored in the dope vector. When we wish to
reference an element A[i;j] we need only compute the variable part
and add it to the constant part.
The dope vector for A [1:M; 1:N] perhaps might contain
.GROUP SKIP 10;
There is another scheme for storing arrays which is used in
some of the Burroughs machines. Each row is stored sequentially and
access to separate rows is made through a device called a
`mother-vector'. The mother vector is a vector of pointers to the
rows. Thus:
.GROUP SKIP 10;
Notice that the accessing computation is very cheap. Another effect
is that all rows need not be in memory at once. On a paging or
segmenting machine (we will talk about machine organization later)
this array organization can be helpful. If an access to a row not in
core is made, a `page fault' is raised; the monitor brings the row
into memory and the computation continues. The mother-vector scheme
generalizes nicely to multidimensionality and can be used in
conjunction with a dope vector.
.END
A typical implementation on an array facility in LISP would include
a declaration:
.BEGIN INDENT 0,10;
⊗→%3array%*↔←%3[%1<identifier>;<type>;<bounds>; ... <bounds>], where the
identifier names the array; the type could be numeric or sexpr; and finally
a declaration of upper and lower bounds for each dimension would be needed.
%3array%* is a special form whose effect is to make the array name a %3SUBR%*,
whose code is the calculation of the dope vector. Thus:
.END
.GROUP SKIP 15;
.BEGIN INDENT 10,10;
If we are to store sexprs in the array then the ⊗→garbage collector↔← must
be able to mark the entries. This is the reason for including type information.
When an array element is to be referenced, then the subscripts are evaluated
(recall that the array name was declared as a %3SUBR%*) and the dope vector code
is executed, resulting in a reference to the appropriate cell.
.END
We also must be able to store information in the array.
.BEGIN INDENT 0,10;
%3store[%1<name>[<subscr>; ... <subscr>];<value>] : ⊗→%3store%*↔← is a special form
whose effect is to store the value of <value> in the designated array element.
.END
.SS(strings and linear LISP,string processor,P27:)
.BEGIN TURN ON "←";
Strings and string processors are an important class
of data structures and algorithms. Powerful string processing is a
necessity for any well developed compiler-writing system. The
organization and implementation of a general string processor
directly parallels LISP. In fact a subset of LISP,
⊗→linear LISP↔←, is a nice notation for string algorithms.
A string is a sequence of characters. A reasonable language
(not PL/1) for string processing should allow the creation of strings
of arbitrary length at runtime; it should allow the generation of new
strings and the decomposition of existing strings. If strings of
arbitrary length are to be created, an organization similar to FS in
LISP can be used with, perhaps, a string garbage collector. We will
assume this most general case.
The machine memory will contain at least a ⊗→string space↔←, an
evaluator, a symbol table, and a garbage collector.
String space is a linear sequence of cells, each of which can
contain exactly one charcter. A string will be represented as a
sequence of sequential character cells. A string variable will be an
entry in the symbol table; the current value of the variable will be
represented as a pair; character count and a pointer to the beginning
of the character sequence.
Thus:
.GROUP SKIP 4;
.BEGIN TURN OFF"←";
We must make some decisions about how we manipulate strings: when we
perform %3x ← y%*, do we copy the symbol table pair of %3y%* into that of %3x%*, or
do we make a new string isomorphic to %3y%* and point %3x%* at it. It makes
a difference. We will choose the former, copying only the
`descriptor', that is, we will share strings (and substrings)
wherever possible. This decision makes the storage requirements less
expensive, but will make our life more difficult when we worry about
⊗→garbage collection↔←. There are three primitive functions: ⊗→%3first%*↔←,
⊗→%3rest%*↔←, ⊗→%3concat%*↔← (read: %3car%*, %3cdr%*, %*cons%*).
.END
.BEGIN INDENT 0,10;
%3first[x]%* is the first
character of the string represented by %3x%*. %3first%* is undefined for the
empty string. For example:
.END
←%3first[ABC]%1 is %3A; first[%1∧%3]%* is undefined.
%3rest[x]%* is the string of characters which remains when the first
character of the string is deleted. %3rest%* is also undefined for the
empty string. For example:
←%3rest[ABC]%* is %3BC%*
.BEGIN INDENT 0,10;
%3concat[x;y]%* is a function of two arguments. %3x%* is a character; %3y%* is
a string. %3concat%* forms a string consisting of the concatenation a
copy of %3x%* and a copy of the string, %3y%*. For example:
.END
←%3concat[A;BC]%* is %3ABC%*
There are three string predicates:
.BEGIN CENTERIT;
←⊗→%3char%*↔←%3[x]%1: is %3x%* a single character?
←⊗→%3null%*↔←%3[x]%1: is %3x%* the empty string?
←%3x ⊗→%3=%*↔← y%1: are %3x%* and %3y%* the same character?
For example:
←%3char[A] %1is true
←%3char[AB] %1is false
←%3AB = AB %1is undefined
.END
Now to implementations:
%3first%* generates a character count of 1 and a pointer to the
first character of the parent string.
%3rest%* generates a character count of one less than that of the
parent and a pointer to the second character of the parent string.
%3concat%* is a bit more problematic. We copy %3x%* and copy %3y%*,
generate a character count of the sum of those of %3x%* and %3y%*, and
generate a pointer to the character of the copy of %3x%*. The copies are
made in the free string space pointed to by the %2⊗→string space pointer↔←%*.
The obvious question of what to do when string space is exhausted
will be postponed for a moment. The implementations of the three
predicates are easy: we will blur the distinction between characters
and strings of length 1. Thus %3char%* need check the character count.
%3null%* says character count is 0. What about = ? Obviously characters
are not stored uniquely, so we must make an actual character
comparison.
Now ⊗→garbage collection↔←. In some ways a string garbage
collector is simpler and in some ways more difficult than a collector
of list-structure. The marking phase is much simpler: using the
descriptor in the symbol table, mark the character string. Since we
are sharing substrings, we cannot stop the marking simply because we
have encountered a previously marked character.
But at least the marking is not recursive. However, the collection
phase needs to be more sophisticated for string processors. Since
strings are stored linearly (or sequentially), a fragmented string
space list is of little use. Thus we must compact all the
referenceable strings into one end of string space, freeing a linear
block for the new free string space. Since we are sharing substrings
a little care needs to be exercised. When we move a string,
obviously the descriptor of any variable referencing any part of that
parent string must be changed to reflect the new location. So before
we begin the relocation of strings we sort the string descriptors on
the basis of their pointers into string space. We then recognize
each parent string, moving it down into freed locations and updating
the address pointers of any substrings. We continue this process.
Eventually all strings will be compacted down in string space. The
free space pointer will be set and the computation can continue.
Compacting garbage collectors can be adapted for use in LISP or more
general types of data structures.
.END
.SS(%3rplaca%* and %3rplacd%*)
.BEGIN TURN ON "←";
We will first look at some LISP coding
tricks which when used judiciously, can increase efficiency, but when
used in a cavalier manner can result in mystery. First, LISP does an
awful lot of copying. Consider:
%3←append <= λ[[x;y][null[x] → y;T → cons[car[x];append[cdr[x];y]]]]%*
This function copies %3x%* onto the front of %3y%*. Note: %3y%* is not copied.
Or recall the %3subst%* function: it generates a copy with the correct
substitutions made. The copying is necessary in general. It keeps
unsavory side effects from happening.
Let's look at %3append[(A B C);(D E F)]%*. It appears that we
could get the appropriate effect of %3append%* by %3cdr%*-ing down the list
%3(A B C)%* until we found the terminator, then replace it with a pointer
to the list %3(D E F)%*. Thus:
.GROUP SKIP 6;
What's wrong here? Consider the sequence of statements:
.BEGIN TABIT1(30);TURN OFF"←";SELECT 3;
\i ← (A,B,C)
\j ← (D,E,F)
\k ← append[i;j]
.END
Then if %3append%* worked as advertised above, (changing the %3cdr%* of the
last element of %3i%*) the following evil would be perpetrated: the value
of %3i%* would be changed surreptitiously!! %3i%* now has the value
%3(A,B,C,D,E,F)%*. Language features which do this are evil. It is,
however, quite useful to be evil sometimes. Notice that any value
which was sharing part of the structure of %3i%* will also be changed.
This can cause real mystery!! Well the world is good, and %3append%* does
not work as above. The LISP function which %2does%* work this way is
called %3nconc%*. It can be defined in terms of a primitive obscene
function, %3rplacd%*. There are two primitive obscene functions:
⊗→%3rplaca%*↔←%3[x;y]%* replace the %3car%*-part of %3x%* with %3y%*.
.GROUP SKIP 6;
⊗→%3rplacd%*↔←%3[x;y]%* replace the %3cdr%*-part of %3x%* with %3y%*.
.GROUP SKIP 6;
Thus %3nconc%* can be defined as:
.BEGIN SELECT 3;TABIT1(20);TURN OFF"←";
nconc <= λ[[x;y]prog\[[z]
\ [null[x] → return[y]];
\ z ← x;
\a[null[cdr[z]] → rplacd[z;y];return [x]];
\ z ←cdr [z];
\ go[a] ]]
.END
These functions must be used with extreme caution. They are not
recommended for amateur hacking. They are introduced here simply to
show that it is possible to improve on the efficiency of pure
algorithms by resorting to these coding tricks.
Consider:
.BEGIN SELECT 3;TABIT1(30);TURN OFF"←";
\x ← (NOTHING CAN GO WRONG);
\rplacd[cdddr[x];cddr[x]];
\print[x];
.END
So we can use %3rplacd%* to generate circular lists (and to generate wall
paper by printing them!!).
Circular lists cannot be generated in LISP without functions like
%3rplaca%* and %3rplacd%*.
See the problem on {yon(P55)}.
In general, to circularize a non-empty
list, %3x%*, %3rplacd[last[x];x]%* suffices where:
←%3last <=λ[[x][null[cdr[x]] → x; T → last[cdr[x]]]]%*
←%2Problems%*
%21.%1 What is the effect of evaluating %3rplacd[x;cdr[x]]%*?
.END
.SS(Applications of %3rplaca%* and %3rplacd%*)
We begin with rather simple examples. Consider the problem of inserting
an element into the middle of a list. For example let %3x%* be the list,
%3(A B C)%*. If we wished to insert an atom, say %3D%*, between %3B%*
and %3C%*, we could perform:
.BEGIN CENTER; SELECT 3;turn off"←";
x ← cons[car[x];cons[cadr[x];cons[D;cddr[x]]]].
.END
Indeed, in general, we have little choice but to recopy the the initial segment
of %3x%*, adding %3D%* into the appropriate place. A similar technique is
obviously available to delete a specified element from the interior of a list.
Careful use of %3rplacd%* can, in some instances, replace the heavy use of %3cons%*.
%3cons%* always carries with it the threat of a call on the garbage collector.
For example, given the list %3(A B C)%* with pointers, %3x%* and %3y%*, into it
as follows,
.GROUP SKIP 5;
we could insert the element, %3D%*, %2after%* the first element in %3y%* by:
←%3rplacd[y;cons[D;cdr[y]]%*, giving:
.GROUP SKIP 5;
(Notice that %2one%* %3cons%* is unavoidable.)
But as always, be warned that the value of %3x%* has also been changed; and
any sexpr sharing the list %3x%* or %3y%* as a sublist has also been affected.
We can also use %3rplacd%* to delete not the %2first%*, but the next element,
in %3y%* by:
←%3rplacd[y;cddr[y]].%*
Similarly, we can use %3rplaca%* to modify an element in a list (or sexpr).
To change the first element in the list, %3y%*, to the sexpr, %3z%* use
←%3rplaca[y;z]%*.
Notice that the uses of %3rplacd%* for insertion and deletion are couched in terms
of insert %2after%* and delete %2after%*, rather than insert %2at%* or delete %2at%*.
If you look at a diagram you will see why:
.GROUP SKIP 7;
To delete the element %3B%* requires modifying the %3cdr%*-part of the predecessor
cell. Similarly to insert at a specified cell. How could we write such modifying
functions? A simple, perhaps inefficient scheme, would be to start another pointer
from the beginning of the list, looking for the cell whose %3cdr%* pointed to the
desired spot; then make the modification.
If these `modification-%2at%*' functions were to be performed very frequently
then it might be worth starting %2two%* pointers down the list, one at %3x%*,
one say %3y%* at %3cdr[x]%*, as above. Then %2testing%* could be done using %3y%*
and the %2modification%* could be done using %3x%*. When we move %3y%* to
%3cdr[y]%* we move %3x%* to %3cdr[x]%*. What happens if we wanted to modify
%2before%* rather that %2at%*? We could proliferate the `back pointers', but
perhaps if this kind of generality is required a change of representation
is called for. More complicated data representations are discussed
in detail in ⊗→Knuth's Kompendium↔←,Khapter 2.
The LISP system uses %3rplaca%* and %3rplacd%* heavily; for example, functions
which modify properties on the p-lists use these functions. Here are
two p-list manipulating functions, ⊗→%3putprop%*↔← and ⊗→%3remprop%*↔←.
.BEGIN INDENT 0,10;
%3putprop%* is a function of three arguments, %3n%*, an atom; %3i%*, an indicator;
and %3v%* a value. The effect of %3putprop%* is to attach the indicator-value pair
to %3n%*. If the indicator is already present then we will simply change its value
to %3v%*; if the indicator is not present then we will add the indicator-value
pair to the front of the p-list. Since %3VALUE%*-cells have a slightly different
format (see {yon(P50)}), there is special glitch for adding or modifying them.
.END
.BEGIN SELECT 3;TABIT2(5,8);GROUP; TURN OFF"←";
putprop <= λ[[n;i;v]
prog[[m]
\\m ← cdr[n];
\a\[eq[car[m];i] → go[b]]
\\m ← cddr[m];
\\[m → go[a]];
\\[eq[i;VALUE] → rplacd[n;cons[VALUE;cons[cons[NIL;v];cdr[n]]]];return[v];
\\ T → rplacd[n;cons[i;cons[v;cdr[n]]]];return[v] ]
\b\[eq[i;VALUE] → rplacd[cadr[m];v];return[v];
\\ T → rplaca[cdr[m];v];return[v]] ]]
.END
Notes:
1. %3[m → go[a]]%* is a trick you have seen before.
2. Extended conditional expressions are used here.
%3remprop%* is simpler.
.BEGIN INDENT 0,10;
%3remprop%* is a predicate, whose importance lies in its side effects. %3remprop%*
has two arguments, %3n%*, an atom, and %3i%*, an indicator. If the indicator is found on the
p-list of the atom, then %3remprop%* removes the indicator-value pair and returns
%3T%*, otherwise %3remprop%* does nothing and returns %3NIL%*.
.END
.BEGIN SELECT 3;TABIT2(5,8);GROUP;TURN OFF"←";
remprop <= λ[[n;i]
prog[[m]
\\m ← n;
\a\[eq[cadr[m;i] → rplacd[m;cddr[m]];return[T]]
\\m ← cddr[m];
\\[m → go[a]]
\\return[NIL] ]]
.END
Applications of %3rplacd%* will occur inside ⊗→%3ratom%*↔← and
inside the ⊗→garbage collector↔←. For example the ⊗→sweep phase↔← might
be described as:
.BEGIN SELECT 3; GROUP;TURN OFF"←"; TABIT2(22,25);
sweep <= λ[[x;y]prog\[[z]
\\z ← NIL;
\a\[nap[x] → z ← rplacd[x;z]]
\\x ← down[x];
\\[eq[x;y] → return[z]]
\\go[a] ]]
.END
Where %3sweep%* is to sweep from %3x%* to %3y%*. %3nap%* is a predicate
returning %3T%* just in the case that its argument is still marked `not available';
and %3down%* finds the `successor' of its argument in the linear ordering of the
memory cells.
As a final example we will describe a ⊗→fixup↔← mechanism (see {yonss(P7)}) using
%3rplacd%*. Since our fixups will be very simple when assembling compiled code,
we will chain the forward references together via their %3cdr%*-parts. If an atom,
%3n%*, is defined to be a label it will have on its p-list, the indicator
%3SYM%* and a value representing the memory location assigned to %3n%*.
In the case of forward references to a label %3n%* two actions may occur.
Let loc be the memory location to be assigned to the instruction containing the
forward reference.
If this is the first occurrence of a forward reference to %3n%*,
then the pair %3(UNDEF .(%* loc%3))%1 is added to the property list, and %30%*
is placed in the %3cdr%*-part of loc and the partial instruction is placed
in the %3car%*-part. Thus:
.GROUP SKIP 5;
Any succeeding references to %3n%* result in changing the %3cdr%* of the
p-list pair, call it v, to point to
a cell whose %3car%*-part is loc and whose %3cdr%*-part is v. As above
we deposit the partial instruction in the %3car%*-part and %30%* in the %3cdr%* part
of loc. Thus the next reference would update our example to:
.GROUP SKIP 10;
When the label %3n%* finally is defined we must perform the fixups,
delete the %3UNDEF%* pair, and add a pair %3(SYM%* . loc %3)%* on the p-list.
.GROUP SKIP 10;
Here are the functions. %3defloc%* is called when a label has been defined;
%3gval%* is called when a label is referenced.
.BEGIN SELECT 3;GROUP;TABIT2(25,32);TURN OFF "←";
defloc <= λ[[lab;loc]prog\[[z]
\\[z ← get[lab;UNDEF] → go[fixup]
\a\return[putprop[lab;loc;SYM]]
\fixup\[null[z] → rplacd[lab;cdddr[lab]];go[a]]
\\deposit[car[z];plus[examine[car[z]];loc]]
\\z ← cdr[z];
\\go[fixup] ]]
.END
.BEGIN SELECT 3;GROUP;TABIT1(15);
gval <= λ[[lab]\[get[lab;SYM];
\ T → putprop[lab;cons[loc;get[sym;UNDEF]];UNDEF]0]]
.END
Notes: %3gval%* is full of pitfalls.
%21%*. %3loc%* is a global variable.
%22%*. There is no e%41%*; we assume that if p%41%* evaluates to something not
equal to %3NIL%*, then that value is the value of the conditional expression.
%23%*. Otherwise the %3putprop%* is executed and %30%* is returned.
See problem III, {yon(P10)}, and problem *** at the end of this section for
the description of a complete assembler for our latest %3compile%*.
←%2Problems%*
assembler
II. More on %3ratom%*.
Recall the discussion of %3ratom%* in {yonss(P13)} and {yonss(P14)}.
Now that you know about %3rplaca%* and %3rplacd%* write a more detailed
version of %3ratom%*.
III. Recall the function which reverses the top-level elements of a list.
On {yon(P16)} and {yon(P23)}
we wrote it in various styles and with varying degrees of efficiency.
All of these functions used %3cons%*; however it is clear that we should be
able to reverse a list without using %2any%* new cells.
Write an AMBIT algorithm for such a reversing function. Express this
algorithm as a LISP function. If you use %3prog%* don't use any %3prog%*-variables.
.SEC(Systems Organization)
There are many applications of data structures which arise
very naturally in the domain of systems programming. This section
will begin with a very brief historical description of systems
organization, from the bare machine to multi-processing.
In the early days of computers, operating systems were
non-existent. You would sign up for a couple of hours of machine
time, appear with your card deck or paper tape, and operate the
machine. Debugging devices consisted of a sharp pointed stick, and a
quick hand on the console switches. This means of programming was
very satifying to many of the programmers, but machine utilization
left something to be desired. Much of the time the machine would
sitt idle (stopped) as you would think about what to do next. As
processing speed and machine costs increased it became evident that
this mode of operation had to go. The first operating systems
consisted of a dull slow object called an operator and a satellite
computer on which an input tape consisting of many separate jobs was
created. Each job on the input tape was swquentially read into
memory, executed and the output presented to an output tape. If some
abnormal behavior was detected in your program, you were also
presented with an often uninspiring octal dump of the contents of
memory. Whenever a job required say, a data tape, the operator would
be notified, and the machine would wait until the tape was located,
mounted, and readied. There was a moderately small resident monitor
which controlled the input, output and perhaps the timing of jobs.
Gross utilization of the machine was increased, however at the cost
of easy debugging. This mode of operation is called batch
processing.
The CPU (central processing unit) still locks up when I/O
devices aren't ready and the user can physically halt the machine.
For this model and most of the future discussion, it simplifies
matters to assume that the monitor resides in a separate core box
from that which contains user programs.
Thus:
.GROUP SKIP 10;
The user programs are loaded into explicit (hard) locations in
memory, and it is assumed that the user has access to all of the
addressing space of his core box.
In an attempt to decrease the overhead on waiting for
external actions (I/O requests or operator intervention) we attach a
reasonably fast storage device (and increase the size of the
monitor). This storage device is capable of holding many user jobs.
Whenever a user (loser) program requires a service which cannot be
satisfied immediately, the monitor will swap the program out of
memory onto this storage device, initiate action which will tend to
satisfy the request, and bring another job into core, beginning its
execution. This new job may either be the next job on the input
stream, or a job which was swapped out and now is ready to run. The
user still is given the whole addressing space, he is still loaded
into explicit memory locations, but the monitor must now be more
cleaver. It must be able to recognize (or `trap') requests which
would lock up the CPU. It must be able to make decisions as to which
job to run next.
.GROUP SKIP 10;
Clearly there are grossinefficiencies in the present scheme.
Allowing, or in fact requiring, that each user have access to all of
memory is too generous. Assume that our memory size is 32→ words and
assume that we have 16K jobs which are ready to run. We should be
able to load one job into locations 0 - (16K-1) and load the other
job into the other half of memory. When one job requires external
service, we should be able to switch the CPU to begin execution of
the other job provided that we save all information about the current
state of the suspended jog. The point is that it takes time to swap
jobs in and out of core so thaat anything we can do to decrease this
overhead is a winner. What are the added requirements for this
scheme? Manily we must have some scheme for keeping the jobs out of
each other's hair. This is usually done by a hardware addition to
the machine called the protection register.
In this simple scheme the protection register would be loaded by the
monitor with the upper and lower bounds on the addressing space
accessible to the current job. Then every memory reference made by a
program is filtered through the protection register. Obviously the
instruction to load protection register should be restricted to
execution by the monitor.
What are the inefficiencies in this scheme? Consider what
happens when we have to swap a job out of memory. Since the
addresses used by the program are explicitly tied to memory
locations, we must swap that job back into exacly the same locations
if it is to run correctly. Consider two 16K programs whose only
effect is to execute `jump-self' loops ( L (JRST L) ). Their initial
load might look like:
.GROUP SKIP 10;
If we swap out the top job and try to swap it back into the lower 16K
at some later time, we lose big.
.GROUP SKIP 10;
But clearly if the bottom 16K is available we should be able to use
it. We want to be able to swap our programs into any available block
of core which is of sufficient size.
To accomplish this we add a new piece of hardware, the
relocation register. Now our loader loads all our programs as if they
begin at location, 0. Thus in the above example:
.GROUP SKIP 10;
To get the appropriate effect when we execute any program, we bias
every memory reference by actual address assigned to the program's
location 0. This bias is put in the relocation register by the
monitor before it begins execution of the program. With this scheme
we can run any jobs in any block of core which is the correct size.
All we need do is load the appropriate offset in the relocation
register.
.GROUP SKIP 10;
Now we can dispense with the two-core box approach. Just use
one box and bias every access in a user program by the length of the
monitor plus the usual offset:
.GROUP SKIP 10;
The actual harrdware can also be simplified now since the lower bound
on every user's addressing space is always zero.
Clearly, more refinements need to be made. At present the
only way to interrupt a job is if he terminates, or calls for some
external action, or attempts to perform some illegal or restricted
instruction. Any operating system needs to be able to monitor the
amount of CPU time spent on a job. So we should have a programmable
clock which can be set by the monitor and which will send an
interrupt to the at a specified time. Actually other hardware needs
to be added to our entourage if we intend to do reasonable
time-sharing. A sophisticated priority interrupt system is a
necessity. Since many of the applications of data structures appear
in time-sharing systems, we will say a bit about the behavior of such
systems.
.SS(Time-sharing organization)
What make time-sharing viable is the tremendous difference
between human reaction time and machine speeds. In a period of a few
seconds a well designed t-s system can satisfy simple requests by
many users. If a user must wait a significant length of time to
obtain a response to a simple command, then your system is in
trouble. The heart of a rapid response is a priority interrupt
system.
A time-sharing monitor must service terminals, mass storage
devices and control the dynamic allocation of its memories.
Consider the care and feeding of a relatively fast storage
device, say a disk, and its interaction with the sending and
receiving of characters from user terminals. Most disks require a
sequence of commands be issued before an actual data transfer can
take place. Assume that there are two commands: a seek to find the
appropriate area on the device, followed by the transfer command. If
the CPU were tied up from the beginning of the seek to the end of the
transfer, significant amounts of CPU time would be lost. If we
issued the seek, went off to do other calculations, but were not
responsive enough when the seek was completed we might miss the
chance to make the transfer due to intervening rotation of the disk.
What we can do is put the disk on a high priority interrupt channel
and the terminal keyboards on a medium priority channel. Issue the
seek, go back to computation, perhaps servicing the keyboards; and
when the disk is in position we will get a high priority interrupt,
freezing the state of the computation; at this time, begin the
transfer of information, dismissing the interrupt and continuing the
computation. Thus higher priority requests can interrupt lower ones;
any lower priority requests must be suspended or saved until the
higher one is completed. You might decide to design the hardware to
allow recursive interrupts on a particular channel or might require
completion before another request can be serviced.
What about the data structures used in a complex system.
Data structures are used heavily in the scheduling algorithms. the
t-s monitor must make decisions about which jobs in the system are to
run. These decisions are based on such simple things as: the job
isn't requesting service--dormant; the job is waiting for some I/O
device--I/O wait; or decisions must be based on more difficult
criteria: the job is ready to run but is too big for the currently
available allotment of core; there is a job ready which needs fast
response or has been waiting inordinately long for service.
In general a vast array of information can be used in
deciding which job to run next. Usually these decisions take shape
by reqquiring that the jobs currently in the system be partitioned
into a finite set of waiting-lines or queues. The scheduling
algorithm manipulates these queues as the status of the jobs change.
A queue is a data structure. Queues are also called first-in
first-out lists (FIFO) or pop-up lists. In LISP parlance you append
new queue-elements to the end of the list and take the elements off
of the front of the list. It should be obvious where the name
waiting-line comes from.
Queues are also used in the buffering schemes of I/O devices.
As we type `LOGIN.....' to a t-s system, it is usually the case that
the character string first goes into a system buffer and when the CPU
is free, the command is decoded. Obviously we want the monitor to
see the character string in the same order in which we typed it.
That is the buffer is acting like a queue.
A queue can be implemented as simply a list with a pointer to
the front, and a pointer to the end. When you add something to the
end, you update one pointer; wen you take an element off the front
you update the other pointer. There is the obvious check to make
sure that you can recognize the empty queue: when the front pointer
meets the end pointer:
.GROUP SKIP 6;
As with stacks, the queue is usually not represented as a list of
argitrary length. A queue can be represented as a sequential set of
memory locations, still with two pointers. What happens when we have
filled the last cell in the sequence. Well, if some process has
been removing items from the queue, then the front pointer has moved:
.GROUP SKIP 6;
In this case the cells from the first cell in the sequence to the
current position of the front pointer are available. Use `em. That
is a queue is usually implemented as a sequential circular list with
two pointers. In this implementation the tests for the empty queue
are slightly more complex, but are still obvious. Notice too, that
we must now also test for the full queue.
In system applications it is usually the case that one
process is filling the queue and one process is emptying it. In this
application, a full queue should simply put the filling process to
`sleep' (or suspend it), and when a queue becomes empty, the emptying
process should be suspended. There are some interesting and
non-trivial problems which arise in connection which such
`cooperating processes'.
There are some interesting data structure applications which
are connected with the allocationa dn (?) liberation of storage. The
monitor must be able to allocate storage to jobs as their
requirements become known and must also be able to recover areas of
memory which are no longer being used. Similarly, since an integral
part of a large system is a file structure, the monitor must be able
to handle the demands of file maintenance. These two problems are
related but solutions for core allocation are not necessarily
reasonable ones for file allocation.